1. Field of the Invention
This invention relates to a system for tracing two and three dimensional contoured surfaces, and for recording and optimizing data points representative of the traced surface. The present invention can automatically record all points along a traced path and discard unnecessary points so as to minimize the file size of the recorded points.
2. Description of the Prior Art
Systems, known as digitizers, for tracing contoured surfaces and storing the representative data points, are well known. In a conventional digitizing scheme, a stylus or tracer is displaceable over a two or three dimensional object to establish the outer dimensions of said object. During the tracing routine, data points representing the surface dimensions of the object are recorded for subsequent use. These data points define a digital abstraction of the original object.
The digitized points can be recorded manually by the operator, or automatically at given time intervals or distance intervals. Manual recording is acceptable if the pattern to be digitized is small or is a relatively straight-edged shape. However, if the shape to be digitized is large and complex, automatic recording is a virtual necessity. An advantage of automatic recording is that many more points can be recorded in a given interval resulting in a more accurate digital representation of the shape. Also, since the operator need not stop his tracing motion to record a point, he can devote his full attention to guiding the stylus around the template.
Although automatic recording reduces the burden on the operator, many unnecessary points may be recorded. Unlike manual recording, wherein the operator records only those points lying along contoured or curved surfaces and does not record multiple points lying on a straight line, automatic recording periodically records points along both straight and contoured surfaces. Thus, automatic recording may result in unnecessary recordation of many points that are not needed for accurate duplication of the traced template. Furthermore, the resulting data file can be very large if the digitized shape is large and/or complex.
In order to alleviate this problem, it is desirable to discard unnecessary data points from the data file. This process is known as optimizing. Optimizing is the technique of compressing a file of digitized coordinate data in order to save memory space. The ideal optimizing routine would discard the maximum number of digitized data points in the fastest possible time without substantially altering the original digitized path.
One method of optimizing is known as playback optimizing. According to this method, a first file of coordinate data corresponding to stylus movement around a template is created. Next, the previous stylus path is repeated or played back according to the original data file, only at a much slower speed. As the arm motion is played back, the operator may designate which data points should be kept. These data points are stored in a second file of coordinate data thereby creating a compressed file of data points. (See, U.S. Pat. No. 4,385,358 to Ito et al.) Of course, this method is extremely slow and subject to error. Further, there must be enough space in the memory means to store both the original data file and the compressed data file simultaneously.
According to another known method of optimization, a first file of coordinate data corresponding to stylus movement around a template is created. Thereafter, a comparator circuit compares data point P.sub.i to data point P.sub.i+1. If the absolute value of the difference is greater than a predetermined offset value, then the latter point is stored in a second file of coordinate data. If the difference is less than the offset, then the point P.sub.i+1 is not stored in the second data file. If P.sub.i+1 is not saved in the second file, then the point P.sub.i is compared to point P.sub.i+2. This process is repeated for every point in the arm motion path. (See, e.g., U.S. Pat. No. 4,385,358 to Ito et al.) The result of this method of optimization is simply to reduce the resolution of the digital image stored in the original file by a factor proportional to the predetermined offset value. Points that could have been discarded without substantially altering the original digitized path will be kept, and points will be discarded that could substantially alter the original digitized path. Furthermore, the memory means must contain sufficient space to store both the original data file and the compressed second file simultaneously.
Thus, the problems associated with conventional optimizer routines make these systems impractical for use with complex template shapes having large data files. Further, while an efficient optimization routine would be advantageous, a digitizer system could be further improved if the data generated by the digitizing apparatus could be stored in a format such as ASCII that could easily be read and manipulated by a simple and inexpensive personal computer ("PC").